class Solution {
public:
    int largestRectangleArea(vector<int> h)
    {
        stack<int> left, right;
        vector<int> v1, v2;

        for (int i = 0; i < h.size(); ++i)
        {
            while (!left.empty() && h[left.top()] >= h[i])
                left.pop();
            if (!left.empty())
                v1.push_back(left.top());
            else
                v1.push_back(-1);

            left.push(i);
        }
        for (int i = h.size() - 1; i >= 0; --i)
        {
            while (!right.empty() && h[right.top()] >= h[i])
                right.pop();
            if (!right.empty())
                v2.push_back(right.top());
            else
                v2.push_back(h.size());

            right.push(i);
        }
        reverse(v2.begin(), v2.end());

        int _max = 0;
        for (int i = 0; i < h.size(); ++i)
        {
            int l = v1[i], r = v2[i];
            _max = max(_max, (r - l - 1) * h[i]);
        }
        return _max;
    }
    int maximalRectangle(vector<string>& matrix) {
        if (matrix.size() == 0)
            return 0;
        int _max = 0;
        vector<int> num(matrix[0].size(), 0);
        for (int i = 0; i < matrix.size(); ++i)
        {
            for (int j = 0; j < matrix[i].size(); ++j)
            {
                int t = matrix[i][j] - '0';
                if (t == 0)
                    num[j] = 0;
                else
                    num[j] += 1;
            }
            _max = max(largestRectangleArea(num), _max);
        }
        return _max;
    }
};